package com.demo698_划分为k个相等的子集;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Solution {


    public static void main(String[] args) {
        int[] ints = {4,3,2,3,5,2,1};
        int k=4;
        boolean b = canPartitionKSubsets(ints, k);
        System.out.println("结果为:"+b);

    }
    public static boolean canPartitionKSubsets(int[] ints, int k) {
        int sum=0;
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < ints.length; i++) {
            sum+=ints[i];
            list.add(ints[i]);
        }

        Collections.sort(list);

        int[] nums = new int[ints.length];

        for (int i = 0; i < list.size(); i++) {
            nums[i]=list.get(i);
        }

        // 特殊判断: 如果总和 不可以被 K 整除, 那么为false
        if (sum%k!=0){
            return false;
        }

        int avg=sum/k; // 每份的总和值, 由于都是正数, 所以, 里面的存在的可能最大的元素就是 大小=avg  ||  1,1,6   k  = 2, avg = 4 ,  所以这行前面分析的有一点问题

        // 特殊判断: 如果数组中的最大元素是 大于 平均值的, 那么也为false
        if (nums[nums.length-1]>avg){
            return false;
        }


        //2.创建k个桶
        int[] buckets = new int[k];
        Arrays.fill(buckets,avg);

        return dfs(nums,nums.length-1,buckets,k); // 倒着来实现
    }

    // 参数1: 数组, 参数2: 数组中当前的第几个元素  参数3: 桶  参数4: 桶的个数    其实第4个参数有点鸡肋
    private static boolean dfs(int[] nums, int startIndex, int[] buckets, int k) {
        //  如果已经是在放下标为 -1 的数组元素, 说明所有的数组元素已经放进了桶里
        if (startIndex==-1){
            return true;
        }

        //  尝试把当前数组元素放进k个桶里, 每次放都是从头开始放
        for (int i = 0; i < k; i++) {
            // 如果上一个桶和这个桶情况相同的话, 则直接跳过
            if (i>=1&& buckets[i]==buckets[i-1]){
                continue;
            }
            // 如果桶余下空间刚好放这个元素, 或者还有空间,  那么就可以放下一个元素
            int temp = nums[startIndex];
            if (buckets[i]-temp>=0){
                // 当前桶的空间减少
                buckets[i]=buckets[i]-temp;
                // 继续放下一个元素: 从数组中倒着取的
                if (dfs(nums,startIndex-1,buckets,k)){
                    // 如果能走到这个if里面来, 也是说明成功了
                    return true;
                }

                // 【回溯】 如果上一步失败了, 说明下一个元素没有找到合适的桶, 是由于这个元素放的这个桶位置不对, 回溯:  之后尝试把该元素放进下一个桶中
                buckets[i]=buckets[i]+temp;
            }else {
                //如果当前桶的剩余空间不足以放该元素, 则遍历下一个桶
            }
        }

        // 走到这里证明没有找到合适的
        return false;
    }
}
